package com.heyqing.topic.GenerateParenthesis_0022;

import java.util.*;

/**
 * ClassName:GenerateParenthesis_0022
 * Package:com.heyqing.topic.GenerateParenthesis_0022
 * Description:
 *
 * @Date:2024/5/20
 * @Author:Heyqing
 */
public class GenerateParenthesis_0022 {
    /**
     * 回溯法
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    /**
     * 实现方法
     * backtracking
     *
     * @param result
     * @param current
     * @param open
     * @param close
     * @param max
     */
    private void backtrack(List<String> result, String current, int open, int close, int max) {
        // 如果已经放置了足够的括号对，且当前字符串是有效的，则将其添加到结果集中
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }
        // 如果还可以放置左括号，则放置一个左括号并继续递归
        if (open < max) {
            backtrack(result, current + "(", open + 1, close, max);
        }
        // 如果已经放置的左括号多于右括号，则放置一个右括号并继续递归
        if (close < open) {
            backtrack(result, current + ")", open, close + 1, max);
        }
    }
}
